package com.company;

public class Main {

    public static void main(String[] args) {
	// write your code here
    }
}
class Solution {
    public int[] sortArray(int[] nums) {
        // insertSort(nums);
        // shellSort(nums);
        //selectSort(nums);
        //selectSort2(nums);
        //heapSort(nums);
        //bubbleSort(nums);
        //quickSort(nums);
        //mergeSort(nums);
        //mergeSortNor(nums);
        countSort(nums);
        return nums;
    }
    //计数排序
    private void countSort(int[] nums){
        int max = nums[0];
        int min = nums[0];
        //求得计数数组长度
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > max) {
                max = nums[i];
            }
            if(nums[i] < min) {
                min = nums[i];
            }
        }
        //计数数组存储
        int[] countNums = new int[max - min + 1];
        for(int i = 0; i < nums.length; i++) {
            countNums[nums[i] - min]++;
        }
        int numsIndex = 0;
        //排序
        for(int i = 0; i < countNums.length; i++) {
            while(countNums[i] > 0) {
                nums[numsIndex++] = i + min;
                countNums[i]--;
            }
        }
    }

    //归并排序
    public void mergeSort(int[] nums) {
        mergeSortSplit(nums,0,nums.length - 1);
    }
    //归并排序非递归实现
    private void mergeSortNor(int[] nums) {
        int gap = 1;
        while(gap < nums.length) {
            for(int i = 0; i < nums.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= nums.length) {
                    mid = nums.length - 1;
                }
                if(right >= nums.length) {
                    right = nums.length - 1;
                }
                merge(nums,left,mid,right);
            }
            gap *= 2;
        }
    }
    private void mergeSortSplit(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSortSplit(nums,left,mid);
        mergeSortSplit(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int tmpIndex = 0;
        int leftIndex = left;
        int rightIndex = mid + 1;
        while(leftIndex <= mid && rightIndex <= right){
            if(nums[leftIndex] < nums[rightIndex]){
                tmp[tmpIndex++] = nums[leftIndex++];
            }else {
                tmp[tmpIndex++] = nums[rightIndex++];
            }
        }

        while(leftIndex <= mid) {
            tmp[tmpIndex++] = nums[leftIndex++];
        }
        while(rightIndex <= right) {
            tmp[tmpIndex++] = nums[rightIndex++];
        }
        for (int i = 0; i < tmpIndex; i++) {
            nums[i+left] = tmp[i];
        }
    }
    //快速排序
    private void quickSort(int[] nums){
        quickNor(nums,0,nums.length-1);
        //quick(nums,0,nums.length-1);
    }
    //快排非递归实现
    private void quickNor(int[] nums, int left, int right) {
        Stack<Integer> stack = new Stack<>();
        int pivot = partitionDig(nums,left,right);
        if(pivot > left + 1){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot < right - 1){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();

            pivot = partitionDig(nums,left,right);
            if(pivot > left + 1){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right - 1){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    private void quick(int[] nums, int left, int right){
        if(left >= right) return;
        if(right - left >= 10){
            insertSortRange(nums,left,right);
            return;
        }
        int pivot = partitionDig(nums,left,right);//左小右大
        quick(nums,left,pivot-1);
        quick(nums,pivot+1,right);
    }
    private int partitionTwoPoint(int[] nums, int left, int right){
        int prev = left;
        int cur = prev + 1;
        while(cur <= right){
            if(nums[cur] < nums[left] && nums[++prev] != nums[cur]){
                swap(nums,cur,prev);
            }
            cur++;
        }
        swap(nums,prev,left);
        return prev;
    }
    public void insertSortRange(int[] array, int start, int end){
        for (int i = start + 1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private int middle(int[] nums, int left, int right){
        int mid = (left + right) / 2;
        if(nums[left] < nums[right]){
            if(nums[mid] < nums[left]) return left;
            if(nums[mid] > nums[right]) return right;
            return mid;
        } else{
            if(nums[mid] < nums[right]) return right;
            if(nums[mid] > nums[left]) return left;
            return mid;
        }
    }
    private int partitionDig(int[] nums,int left, int right){
        swap(nums,middle(nums,left,right),left);
        int tmp = nums[left];
        while(left < right){
            while(left < right && nums[right] >= tmp){
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= tmp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = tmp;
        return left;
    }

    private  int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpLeft = left;
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpLeft);
        return left;
    }
    private int partition(int[] nums, int left, int right){
        int tmp = nums[left];
        int start = left;
        while(left < right){
            while(left < right && nums[right] >= tmp){
                right--;
            }
            while(left < right && nums[left] <= tmp){
                left++;
            }
            swap(nums,left,right);
        }

        swap(nums,left,start);
        return left;
    }
    //冒泡排序
    private void bubbleSort(int[] nums){
        for(int i = 0; i < nums.length; i++){
            boolean flag = true;
            for(int j = 0; j < nums.length - 1 - i; j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j+1,j);
                    flag = false;
                }
            }
            if(flag){
                return;
            }
        }
    }
    //堆排序
    private void heapSort(int[] nums){
        createHeap(nums);
        int end = nums.length - 1;
        while(end > 0){
            swap(nums,0,end);
            shiftDown(nums,0,end);
            end--;
        }
    }
    private void createHeap(int[] nums){
        for(int parent = (nums.length - 1 - 1) / 2; parent >= 0; parent--){
            shiftDown(nums,parent,nums.length);
        }
    }
    private void shiftDown(int[] nums, int parent, int length){
        int child = parent * 2 + 1;
        while(length > child){
            if(child + 1 < length && nums[child + 1] > nums[child]){
                child++;
            }
            if(nums[child] > nums[parent]){
                swap(nums,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    //选择排序
    private void selectSort2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;

            for(int j = left + 1;j <= right; j++){
                if(nums[j] < nums[minIndex]){
                    minIndex = j;
                }
                if(nums[j] > nums[maxIndex]){
                    maxIndex = j;
                }
            }
            swap(nums,minIndex,left);
            //排除最大值在走边被换走了
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(nums,maxIndex,right);
            left++;
            right--;
        }
    }
    // 选择排序
    private void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums, i, minIndex);
        }
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    // 直接插入排序
    private void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (nums[j] > tmp) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = tmp;
        }
    }

    // 希尔排序
    private void shellSort(int[] nums) {
        int gap = nums.length;
        while (gap >= 1) {
            gap /= 2;
            shell(nums, gap);
        }
    }

    private void shell(int[] nums, int gap) {
        for (int i = gap; i < nums.length; i++) {
            int tmp = nums[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (nums[j] > tmp) {
                    nums[j + gap] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + gap] = tmp;
        }
    }
}